Minimum Spanning Tree
Q31.
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:Kruskal's algorithm for finding a minimum spanning tree of a weighted graph G with n vertices and m edges has the time complexity of:Q32.
What is the largest integer m such that every simple connected graph with n vertices and n edges contains at least m different spanning trees ?Q33.
G = (V,E) is an undirected simple graph in which each edge has a distinct weight,and e is a particular edgeof G. Which of the following statements about the minimum spanning trees (MSTs) of G is/are TRUE? I. If e is the lightest edge of some cycle in G, then every MST of G includes e II. If e is the heaviest edge of some cycle in G, then every MST of G excludes eQ34.
Let G be a connected undirected graph of 100 vertices and 300 edges. The weight of a minimum spanning tree of G is 500. When the weight of each edge of G is increased by five, the weight of a minimum spanning tree becomes ________.Q36.
Let G(V, E) be a directed graph, where V = \{1, 2, 3, 4, 5 \} is the set of vertices and E is the set of directed edges, as defined by the following adjacency matrix A.A[i][j]= \left \{ \begin{matrix} 1 &1 \leq j \leq i \leq 5 \\ 0& otherwise \end{matrix} \right. A[i][j]=1 indicates a directed edge from node i to node j . A directed spanning tree of G , rooted at r \in V , is defined as a subgraph T of G such that the undirected version of T is a tree, and T contains a directed path from r to every other vertex in V . The number of such directed spanning trees rooted at vertex 5 is ____